In the latter half of the twentieth century, there began a phenomenon known as the information revolution. While the information revolution is a historical development broader in scope than any one event or machine, no single device has come to represent the information revolution more than the digital electronic computer. The development of computer systems has surely been a revolution. Each year, computer systems grow faster, store more data, and provide more applications to their users.
At the heart of a computer system is one or more central processing units (CPUs), also called processors, which execute instructions stored in the computer's memory. From the standpoint of the computer's hardware, most systems operate in fundamentally the same manner. Processors are capable of performing a defined set of very simple operations, such as arithmetic, logical comparisons, and movement of data from one location to another. But each operation is performed very quickly. Computer program code at multiple levels directs the computer to perform massive numbers of these simple operations, enabling the computer to perform complex tasks. Although the defined set of simple operations is limited, the possible sequences and combinations of such operations which can be specified in the program code are virtually limitless.
In the very early history of the digital computer, computer programs which instructed the computer to perform some task were written in a form directly executable by the computer's processor. Such programs were very difficult for a human to write, understand and maintain, even when performing relatively simple tasks. As the number and complexity of such programs grew, this method became clearly unworkable. To make computer programs easier to develop, a large and varied set of high-level languages was developed for supporting the creation of computer program code.
High-level languages vary in their characteristics, but all such languages are intended to make it easier for a human to write a program to perform some task. Typically, high-level languages represent operations, fixed values, variables, and other constructs in a manner readily understandable to the human programmer rather than the computer. Such programs are not directly executable by the computer's processor. In order to run on the computer, the programs must first be transformed from a human-readable form (source code) to something executable by the processor of a computer, i.e. to a sequence of instructions directly readable and executable by the processor.
An instruction which is directly readable and executable by the processor (a processor-executable instruction) is a sequence of binary bits in a pre-defined format, each bit position being specific to logic within the processor which reads and decodes it. Combinations of bit values specify an operation or operations to be performed, source or destination of data, branch conditions or destinations, and so forth. The bit sequence formatting and the meaning of the bit combinations defines the “instruction set” of the processor. While the limited set of simple operations performed by any processor is similar to that of another, the instruction set of each processor (i.e., the pre-defined format and meaning of the processor's executable instruction binary bit sequence) is not.
In general, source code is universal and understandable by anyone trained to use the applicable language, while executable code is specific to a particular computer system environment, and can only execute on that computer system or one similarly configured. In particular, the executable code is specific to the processor's instruction set, although it may be specific to other parameters of the computer system as well.
Various techniques exist for transforming the source code in a high-level language to processor-executable instructions in the processor's instruction set. Source code can be “interpreted”, meaning that a special program (an “interpreter”) takes each source code statement in sequence, and executes a small procedure (i.e., series of instructions in the processor-executable instruction set) corresponding to each source code instruction. Interpreting is useful for some purposes, but it is generally rather inefficient.
Traditionally, for greater execution efficiency, individual portions (modules) of source code are compiled to form modules of processor-executable instructions, which may be linked together to form larger programs (although some programs contain only a single compiled module). These programs are saved in digital media storage in executable form, and may be distributed in that form to other computer systems, or remain on the system in which they were first compiled. In this form they are later executed, usually many times. Compilation is itself a task performed by a special computer program (a compiler), and can take significant time. Often, compilation involves certain optimizations to the executable code which require analysis of the various instruction sequences within the program. Unlike interpreted code, the resultant processor-executable instructions in a compiled module do not necessarily correspond to particular source instructions, and do not necessarily follow the same sequence, although they must produce the same logical output. Since it is expected that such programs will be executed many times, the burden of compilation is spread over many executions. This traditional form of compilation is sometimes referred to as “static compilation”.
In recent years, there has been increasing interest in “just-in-time” dynamic compilation or optimization. Like static compilation, “just-in-time” or dynamic compilation/optimization involves the generation of optimized processor-executable instructions. But unlike static compilation, the program's processor-executable instructions are generated during or as part of execution of the program of which the processor-executable instructions are a part (the “target program”). This effectively means that just-in-time or dynamic compilation/optimization is intended to be performed many times, for example, each time the program is executed, or for each user process which executes the program.
Obviously, when compared with traditional static compilation, dynamic compilation/optimization suffers from the drawback that it is performed again each time the program is executed or for each new user process. However, there are various advantages to just-in-time or dynamic compilation/optimization that make it attractive in many circumstances. For example, dynamically compiled code is generated on the system that will execute it, and can be generated from a universal, intermediate level code form (between a high-level source language and a processor-executable form), which facilitates portability of the program. Such an approach is frequently used in the well-known JAVA™ virtual machine environment. Furthermore, additional knowledge available to the system at execution time, such as the exact system configuration, the code modules being used, and the actual pattern of code execution, make it possible to generate more efficient compiled code than can typically be generated using a static compiler. Such additional knowledge is particularly effective in the case of actual code usage patterns, which allow dynamic compilation/optimization to focus on optimizing specific portions of the code.
One form of dynamic compilation is the generation of processor-executable instructions at execution time from previously compiled executable code, generally without use of the original source code. This is known as dynamic binary optimization. Dynamic binary optimization is commonly used to emulate a computer system having a different, often older, instruction set architecture. I.e., an executable computer program which was previously compiled to contain processor-executable instructions in an older instruction set architecture can be recompiled from the previously complied executable code to generate processor-executable instructions in the instruction set of the current processor.
Although dynamic binary optimization is commonly used to support emulation, it has the potential for improving execution efficiency even where the originally compiled executable code is compiled to the same instruction set architecture as that of the current processor. In other words, even though the previously compiled version of the program is fully capable of execution on the current processor without further compilation, optimization or translation, the execution efficiencies which are possible through dynamic binary optimization may in some circumstances justify the additional overhead of dynamically re-compiling the already compiled code. In some cases, these execution efficiencies may be magnified if the instruction set architecture has been enhanced with new features not utilized by the original statically compiled code (which may be quite old). Typically, only selective portions of the previously compiled code will be re-compiled dynamically, because one of the advantages of dynamic compilation is that it can identify “hot spots” (frequently executed code portions) and focus optimization activity on these hot spots.
Dynamic binary optimization could find more widespread acceptance in a variety of computing applications if it could be improved. One way in which conventional dynamic binary optimization falls short of its potential, not necessarily generally recognized, is its inability to perform certain optimizations for lack of aliasing information indicating which program variables are potentially referenced by each of the program's instructions. A compiler which produces executable code directly from source code inherently has aliasing information available to it from the source. Often, this information is also preserved in the intermediate code versions as well. Aliasing information enables the compiler to determine which memory locations are potentially referenced by an instruction which references a location in memory, referred to as a memory reference instruction. Examples of memory reference instructions are a load (of data from a memory location to a register) and a store (of data from a register to a memory location). During compilation, such information is useful in determining whether it is possible to re-order certain operations for more efficient code execution.
However, a dynamic binary optimizer typically produces executable code from other executable code. Executable code may, for example, store a value in a first register at an address derived from the values in one or more other registers. It is difficult for the optimizer in these circumstance to know where the first register value is being stored or what the memory destination represents. The dynamic binary optimizer therefore must make conservative assumptions with respect to re-ordering of operations. As a result, it is often unable to re-order operations to increase code execution efficiency for lack of aliasing knowledge, when in fact it would have been safe to re-order the operations had the optimizer had greater knowledge.
A need exists, not necessarily recognized, for a better mechanism to support dynamic binary optimization, and particularly to support dynamic binary optimization by providing greater aliasing information.